package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/find-the-duplicate-number/
 *  寻找重复数 二分法、二进制、快慢指针（没整明白）
 * author: hongchen.liao
 * date:  2022/8/24
 */
public class _287_Find_the_Duplicate_Number {

    class Solution {
        public int findDuplicate(int[] nums) {
            int n = nums.length;
            int l = 1, r = n-1, ans = -1;
            while( l <= r){
                int mid = (l+r) >> 1;
                int cnt = 0;
                for(int i = 0; i < n; i++){
                    if(nums[i] <= mid){
                        cnt++;
                    }
                }
                if(cnt <= mid){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                    ans = mid;
                }
            }
            return ans;
        }
    }

}
